package com.itheima.algorithm.sort;

import java.util.Arrays;

public class HeapSort {

    public static void sort(int [] a){
        //先建立大顶堆
        heapify(a,a.length);
        //每次都将最大的堆顶交换到最后，然后找到新的堆顶
        for(int right=a.length-1;right>0;right--){
            swap(a,0,right);
            down(a,0,right);
        }
    }
    //建堆
    private static void heapify(int[] array,int size){
        //如何找到最后的非叶子节点 size/2-1;
        for(int i=size/2-1;i>=0;i--){
            //下潜操作
            down(array,i,size);
        }
    }
    //将parent索引处的元素下潜：与两个孩子比较，直至没有孩子比他大
    private static void down(int[] array,int parent,int size){
        while(true){
            int left=parent*2+1;
            int right=left+1;
            int max=parent;
            if(left<size && array[left]>array[max]){
                max=left;
            }
            if(right<size && array[right]>array[max]){
                max=right;
            }
            if(max==parent){
                break;
            }
            swap(array,max,parent);
            parent=max;
        }

    }
    //交换两个索引处的元素
    private static void swap(int[] array, int i, int j){
        int t=array[i];
        array[i]=array[j];
        array[j]=t;
    }

    public static void main(String[] args) {
        int[] a={6,5,4,3,2,1};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
